package TestDemo5;

import java.util.ArrayList;

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
public class Test {

    public static TreeLinkNode createTree(){
        TreeLinkNode root=new TreeLinkNode(5);
        TreeLinkNode temp=new TreeLinkNode(4);
        root.left=temp;
        temp.next=root;
        TreeLinkNode temp2=new TreeLinkNode(3);
        temp.left=temp2;
        temp2.next=temp;
        TreeLinkNode temp3=new TreeLinkNode(2);
        temp2.left=temp3;
        temp3.next=temp2;
        return root;
    }

    public static TreeLinkNode findRoot(TreeLinkNode node) {
        if (node.next == null) return node;
        while (node.next != null) {
            node = node.next;
        }
        return node;
    }

    public static void inOrederTraversal(TreeLinkNode root, ArrayList<TreeLinkNode> arr) {
        if (root == null) return;
        inOrederTraversal(root.left, arr);
        arr.add(root);
        inOrederTraversal(root.right, arr);
    }
    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode.left == null && pNode.right == null && pNode.next==null) return null;
        TreeLinkNode root = findRoot(pNode);
        ArrayList<TreeLinkNode> arr = new ArrayList();
        inOrederTraversal(root, arr);
        if (arr.get(arr.size() - 1) == pNode) return null;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i) == pNode) {
                return arr.get(i + 1);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        TreeLinkNode root=createTree();
        GetNext(root.left.left.left);
    }

}
